package com.itheima.algorithm.hashtable;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * @author: TylerZhong
 * @description:
 */
public class E03Leetcode49 {

    /**
     * 思路
     * 1. 遍历字符串数组，每个字符串中的重新排序后作为 key
     * 2. 所谓分组，其实就是准备一个集合，把这些单词加入到 key 相同集合中
     * 3. 返回分组结果
     */
    public List<List<String>> groupAnagrams1(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String key = new String(charArray);
            List<String> list = map.computeIfAbsent(key, k -> new ArrayList<>());
            list.add(str);
        }
        return new ArrayList<>(map.values());
    }

    class ArrayKey{
        int[] key = new int[26];

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof ArrayKey key1)) return false;
            return Arrays.equals(key, key1.key);
        }

        @Override
        public int hashCode() {
            return Arrays.hashCode(key);
        }

        public ArrayKey(String str) {
            char[] charArray = str.toCharArray();
            for (char ch : charArray) {
                key[ch - 97]++;
            }
        }
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<ArrayKey, List<String>> map = new HashMap<>();
        for (String str : strs) {
            ArrayKey key = new ArrayKey(str);
            List<String> list = map.computeIfAbsent(key, k -> new ArrayList<>());
//            System.out.println(Arrays.toString(key.key));
            list.add(str);
        }
        return new ArrayList<>(map.values());
    }

    public static void main(String[] args) {
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> lists = new E03Leetcode49().groupAnagrams(strs);
        System.out.println(lists);
    }
}
